package 二叉树;

public class Solution15 {
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        //异侧或者到了本身
        if(root.val==p.val||root.val==q.val||(root.val>p.val&&root.val<q.val)||(root.val<p.val&&root.val>q.val)) return root;
        //同侧
        return p.val<root.val?lowestCommonAncestor1(root.left, p, q):lowestCommonAncestor1(root.right, p, q);
    }

    //同样的，看哪个更好理解
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < root.val && q.val < root.val) return lowestCommonAncestor2(root.left, p, q);
        if (p.val > root.val && q.val > root.val) return lowestCommonAncestor2(root.right, p, q);
        return root;
    }
}
